Many websites that provide search functionality also provide an auto-completion functionality for search queries. When a user begins to type a search query in a search box, the auto-completion functionality allows users to see a list of suggested search queries, which can eliminate the need to type in the full search query, and/or can show the user how to form improved search queries. A challenge in implementing the auto-completion functionality is to provide the suggested search queries fast enough to deliver suggestions while the user is typing and before the user finishes typing the search query. When the scope of the search engine is broad, with very large numbers of possible queries and search suggestions, the challenge of implementing the auto-completion functionality in a rapid manner can become difficult. In many conventional implementations of auto-completion, adding new search queries and solutions further slows the system.
One common approach to implementing auto-completion is to use a trie data structure. Using a trie data structure for the full set of alphanumeric characters, however, results in rapid fan-out at each level of the tree, and is thus very memory intensive. Additionally, the trie data structure wastes a significant amount of memory, as many of the alphanumeric characters are not used at many of the nodes of the trie data structure. Pre-caching the trie data structure can use a huge amount of memory. Another common approach to implementing auto-completion is to use a ternary tree data structure. Performing auto-completion using a ternary tree data structure consumes less memory, but is significantly slower than using a trie data structure. A challenge is to implement auto-completion in a way that is both fast and memory efficient.
For simplicity and clarity of illustration, the drawing figures illustrate the general manner of construction, and descriptions and details of well-known features and techniques may be omitted to avoid unnecessarily obscuring the present disclosure. Additionally, elements in the drawing figures are not necessarily drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help improve understanding of embodiments of the present disclosure. The same reference numerals in different figures denote the same elements.
The terms “first,” “second,” “third,” “fourth,” and the like in the description and in the claims, if any, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments described herein are, for example, capable of operation in sequences other than those illustrated or otherwise described herein. Furthermore, the terms “include,” and “have,” and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, device, or apparatus that comprises a list of elements is not necessarily limited to those elements, but may include other elements not expressly listed or inherent to such process, method, system, article, device, or apparatus.
The terms “left,” “right,” “front,” “back,” “top,” “bottom,” “over,” “under,” and the like in the description and in the claims, if any, are used for descriptive purposes and not necessarily for describing permanent relative positions. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments of the apparatus, methods, and/or articles of manufacture described herein are, for example, capable of operation in other orientations than those illustrated or otherwise described herein.
The terms “couple,” “coupled,” “couples,” “coupling,” and the like should be broadly understood and refer to connecting two or more elements mechanically and/or otherwise. Two or more electrical elements may be electrically coupled together, but not be mechanically or otherwise coupled together. Coupling may be for any length of time, e.g., permanent or semi-permanent or only for an instant. “Electrical coupling” and the like should be broadly understood and include electrical coupling of all types. The absence of the word “removably,” “removable,” and the like near the word “coupled,” and the like does not mean that the coupling, etc. in question is or is not removable.
As defined herein, two or more elements are “integral” if they are comprised of the same piece of material. As defined herein, two or more elements are “non-integral” if each is comprised of a different piece of material.
As defined herein, “approximately” can, in some embodiments, mean within plus or minus ten percent of the stated value. In other embodiments, “approximately” can mean within plus or minus five percent of the stated value. In further embodiments, “approximately” can mean within plus or minus three percent of the stated value. In yet other embodiments, “approximately” can mean within plus or minus one percent of the stated value.